/*给一非空的单词列表，返回前 k 个出现次数最多的单词。
* 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
*
* 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
* 输出: ["i", "love"]
* 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
* 注意，按字母顺序 "i" 在 "love" 之前。
* */

package newcoder.Heap_2;

import java.util.*;

public class Leetcode692 {

    public static void main(String[] args) {

        Leetcode692 obj = new Leetcode692();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        System.out.println(obj.topKFrequent(words, k));
    }

    public List<String> topKFrequent(String[] words, int k){

        HashMap<String, Integer> map = new HashMap<>();
        int len = words.length;
        for (int i = 0;i < len;i++){
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        //优先队列，给插入队列的值进行优先级赋值
        //PriorityQueue是线程不安全的
        PriorityQueue<String> res = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (map.get(o1).equals(map.get(o2))){
                    return o2.compareTo(o1);
                }else {
                    return map.get(o1) - map.get(o2);
                }
            }
        });

        //大小为k的最小优先队列，如果队列的大小大于k了，则弹出队列中最小的值
        for (String s : map.keySet()){
            res.offer(s);
            if (res.size() > k){
                res.poll();
            }
        }

        List<String> l = new ArrayList<>();
        while (res.size() > 0){
            l.add(res.poll());
        }
        Collections.reverse(l);
        return l;
    }
}
